package binary_tree;

public class MyBinaryTree {
    private static class Node {
        private char val;
        private Node left;
        private Node right;

        public Node(char val) {
            this.val = val;
        }
    }
        public Node buildAtree(){
            Node nodeA=new Node('A');
            Node nodeB=new Node('B');
            Node nodeC=new Node('C');
            Node nodeD=new Node('D');
            Node nodeE=new Node('E');
            Node nodeF=new Node('F');
            Node nodeG=new Node('G');
            Node nodeH=new Node('H');
            Node nodeI=new Node('I');
            nodeA.left=nodeB;
            nodeA.right=nodeC;
            nodeB.left=nodeD;
            nodeB.right=nodeE;
            nodeE.left=nodeG;
            nodeE.right=nodeH;
            nodeH.left=nodeI;
            nodeC.right=nodeF;
            return nodeA;
        }
        //先序进行二叉树的输出
        public void preOrder(Node root){
            if(root==null){
                return;
            }
            System.out.println(root.val+" ");
             preOrder(root.left);
             preOrder(root.right);
        }
        //中序进行二叉树的输出
        public void inOrder(Node root){
            if(root==null){
                return;
            }
            inOrder(root.left);
            System.out.println(root.val+" ");
            inOrder(root.right);
        }
        //后续进行二叉树的输出
        public void postOrder(Node root){
            if(root==null){
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.println(root.val+" ");
        }
        /**
         * 传入一个二叉树的根节点，求出该二叉树的节点个数
         * @param root 二叉树的根节点
         * @return
         */
        public int  getNodeCount(Node root){
            if(root==null){
                return 0;
            }
            return 1+getNodeCount(root.left)+getNodeCount(root.right);
        }
        /**
         * 传入一个二叉树根节点root，就能求得该二叉树的叶子节点个数
         * @param root 传入根节点
         * @return
         */
        public int getleafNodeCount(Node root){
            if(root==null){
                return 0;
            }
            if(root.left==null&&root.right==null){
                return 1;
            }
            return getleafNodeCount(root.right)+getNodeCount(root.left);
        }
        /**
         * 传入一个根节点root，就能求得该树高度
         * @param root 传入二叉树根节点
         * @return
         */
        public int height(Node root){
            if(root==null){
                return 0;
            }
            return 1+ Math .max(height(root.left),height(root.right));
        }
        /**
         * 判断一颗以root为根节点的二叉树中是否包含值为val的节点
         * @param root
         * @param val
         * @return
         */
        public boolean contains(Node root,int val){
            if(root==null){
                return false;
            }
            if(root.val==val){
                return true;
            }
            return contains(root.left,val)||contains(root.right,val);
        }
        /**
         * 传入一个二叉树的根节点root，求出第k层节点个数
         * @param root
         * @param k
         * @return
         */
        public int getKLevelNode(Node root,int k){
            if(k<=0||root==null){
                return 0;
            }
            if (k==1){
                return 1;
            }
            return getKLevelNode(root.right,k-1)+getKLevelNode(root.left,k-1);
        }

        public static void main(String[] args) {
            MyBinaryTree myBinaryTree=new MyBinaryTree();
            Node root=myBinaryTree.buildAtree();
            System.out.println("先序遍历结果：");
            myBinaryTree.preOrder(root);
            System.out.println( );
            System.out.println("__________________");
            System.out.println("中序遍历结果：");
            myBinaryTree.inOrder(root);
            System.out.println( );
            System.out.println("__________________");
            System.out.println("后序遍历结果：");
            myBinaryTree.postOrder(root);
            System.out.println( );
            System.out.println("__________________");
            System.out.println("二叉树结点的个数");
            System.out.println(myBinaryTree.getNodeCount(root));
            System.out.println("二叉树的叶子结点个数为");
            System.out.println(myBinaryTree.getleafNodeCount(root));
            System.out.println("二叉树的高度");
            System.out.println(myBinaryTree.height(root));
            System.out.println("查找二叉树中的元素");
            System.out.println(myBinaryTree.contains(root,'F'));
            System.out.println(myBinaryTree.contains(root,'M'));
            System.out.println("查找深度为K的节点的个数");
            System.out.println(myBinaryTree.getKLevelNode(root,3));
        }
    }
